package 算法.NiuKe.JZ;

import 算法.NiuKe.TreeNode;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * @author:谢君臣
 * @Date:2021/4/2816:26
 * @version:1.0
 * @function:   给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。
 */
public class JZ63 {
    public static void main(String[] args) {
        TreeNode treeNode = Deserialize("5,3,7,2,4,6,8");
        KthNode(treeNode,3);
    }
    static TreeNode Deserialize(String str) {
        if (str.length()<1)
            return null;
        if (str.endsWith(",")) {
            str = str.substring(0,str.length()-1);
        }
        String[] split = str.split(",");
        TreeNode root = null;
        Queue<TreeNode> queue = new ArrayDeque<>();
        if (split.length < 1)
            return root;
        root = new TreeNode(Integer.parseInt(split[0]));
        queue.add(root);
        for (int i = 1; i < split.length; i = i+2) {
            TreeNode poll = queue.poll();
            poll.left = createNode(split[i]);
            try {
                poll.right = createNode(split[i+1]); // 可能越界
            } catch (Exception e) {
                poll.right=null;
            }
            if (poll.left!=null) queue.add(poll.left);
            if (poll.right!=null) queue.add(poll.right);
        }
        return root;
    }
    private static TreeNode createNode(String s){
        if (s.equals("#"))
            return null;
        else
            return new TreeNode(Integer.parseInt(s));
    }
    static TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot==null)
            return null;
        Stack<TreeNode> stack = new Stack<>();
        while (pRoot!=null||!stack.isEmpty()){
            while (pRoot!=null){
                stack.push(pRoot);
                pRoot = pRoot.left;
            }
            if (!stack.isEmpty()){
                if (pRoot==null){
                    pRoot = stack.pop();
                    if (k>1)k--;
                    else return pRoot;
                }
                pRoot = pRoot.right;
            }
        }
        return null;
    }
}
